package Test;

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

//某班级 n 位同学的学号为 0 ~ n-1。点名结果记录于升序数组 records。
// 假定仅有一位同学缺席，请返回他的学号。
//
//
//示例 1：
//
//输入：records = [0,1,2,3,5]
//输出：4
//示例 2：
//
//输入：records = [0, 1, 2, 3, 4, 5, 6, 8]
//输出：7
public class TwentySix {
//方法一：数学求和法
//思路：计算0到n-1的总和，然后减去数组中所有元素的总和，差值即为缺失的学号。
class Solution {
    public int findMissing(int[] records) {
        int n = records.length + 1;
        int expectedSum = n * (n - 1) / 2;
        int actualSum = Arrays.stream(records).sum();
        return expectedSum - actualSum;
    }
}

    //方法二：异或运算
    //思路：利用异或的性质，将所有元素和0到n-1的数依次异或，最终结果即为缺失的学号。
    class Solution1 {
        public int findMissing(int[] records) {
            int xorAll = 0;
            int n = records.length + 1;
            for (int i = 0; i < n; i++) {
                xorAll ^= i;
            }
            for (int num : records) {
                xorAll ^= num;
            }
            return xorAll;
        }
    }
    //方法三：二分查找
    //思路：通过二分查找找到第一个使得recordsmid > mid
    // 的位置，该位置即为缺失的学号。需处理数组元素全部连续的情况。
    class Solution2 {
        public int findMissing(int[] records) {
            if (records == null || records.length == 0) {
                return 0;
            }
            int left = 0, right = records.length - 1;
            while (left < right) {
                int mid = left + (right - left) / 2;
                if (records[mid] == mid) {
                    left = mid + 1;
                } else {
                    right = mid;
                }
            }
            return records[left] == left ? left + 1 : left;
        }
    }
    //方法四：遍历索引比较
    //思路：遍历数组，若当前元素的值不等于其索引，则该索引即为缺失的学号。
    // 若所有元素均正确，则缺失值为数组长度。
    class Solution3 {
        public int findMissing(int[] records) {
            for (int i = 0; i < records.length; i++) {
                if (records[i] != i) {
                    return i;
                }
            }
            return records.length;
        }
    }
    //方法五：哈希集合
    //思路：将数组元素存入集合，然后遍历0到n-1，找出不在集合中的数。
    class Solution4 {
        public int findMissing(int[] records) {
            Set<Integer> set = new HashSet<>();
            for (int num : records) {
                set.add(num);
            }
            for (int i = 0; i <= records.length; i++) {
                if (!set.contains(i)) {
                    return i;
                }
            }
            return -1; // 理论上不会执行
        }

    }
}
